#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2019/1/22 11:58
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 高级-被围绕的区域.py
# @Software: PyCharm
from utils.main import main, opt_list


class Solution:
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        state = {}
        block = {}
        i, j = 0, 0
        n = len(board)
        if n <= 0:
            return
        m = len(board[0])
        s = 0
        while i < n and j < m:
            if board[i][j] == 'O' and not state.get((i, j)):
                s += 1
                block[s] = [True, [], ]

                def search(x, y):
                    state[(x, y)] = s
                    if x == 0 or x == n-1 \
                            or y == 0 or y == m-1:
                        block[s][0] = False
                    block[s][1].append((x, y))
                    step = [
                        (0, 1),
                        (1, 0),
                        (0, -1),
                        (-1, 0)
                    ]
                    for p in step:
                        xx, yy = x+p[0], y+p[1]
                        if 0 <= xx < n and 0 <= yy < m \
                                and not state.get((xx, yy)) \
                                and board[xx][yy] == 'O':
                            search(xx, yy)
                search(i, j)
            if j+1 < m:
                j += 1
            else:
                i, j = i+1, 0
        for key in block:
            value = block[key]
            if value[0]:
                for v in value[1]:
                    board[v[0]][v[1]] = 'X'


def opt(board):
    solve = Solution()
    print(board)
    print('ans:')
    solve.solve(board=board)
    print(board)


def opt1():
    board = [["X", "X", "X", "X"], ["X", "O", "O", "X"], ["X", "X", "O", "X"], ["X", "O", "X", "X"]]
    opt(board=board)


if __name__ == '__main__':
    opt_list.append(opt1)
    main()

